/**
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 *
 * 示例 1：
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 *
 * 示例 2：
 * 输入：head = [1,1,1,2,3]
 * 输出：[2,3]
 *
 * 提示：
 * 链表中节点数目在范围 [0, 300] 内
 * -100 <= Node.val <= 100
 * 题目数据保证链表已经按升序 排列
 */

/**
 * 一次遍历, 遇到相同的就向后继续遍历, 这里面我们要注意一个细节
 * 就是当我们将节点加入虚拟头结点的时候, 要将后面的置为 null
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public ListNode deleteDuplicates(ListNode head) {

        // 虚拟头结点
        ListNode newHead = new ListNode(0);

        // 遍历前的准备
        /**
         * tmp : 用来代表头结点
         * cur : 当前节点的后一个节点
         * prev : 当前节点
         */
        ListNode tmp = newHead;
        ListNode cur = head;
        ListNode prev = head;

        while (cur != null) {

            // 一次遍历
            // 提前向后面移动一个
            cur = cur.next;

            // 这里我们也要注意 cur 的不能为 null
            if (cur == null || cur.val != prev.val) {

                // 不同就加入当前节点
                tmp.next = prev;

                // 这里不要忘记将当前节点的后面置为 null
                prev.next = null;

                tmp = prev;
                prev = cur;

            } else {

                // 相同就一直遍历到不相同的节点
                // 这里也要判断 cur 不能为 null
                while (cur != null && cur.val == prev.val) {
                    cur = cur.next;
                }
                prev = cur;
            }
        }

        // 返回 虚拟接点的后面一个节点
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}